package com.algorithm.动态规划;

/**
 * leetcode_322_零钱兑换:https://leetcode-cn.com/problems/coin-change/
 * 假设有25分、20分、5分、1分的硬币，现要找给客户41分的零钱，如何办到硬币个数最少?
 * - 此前用贪心策略得到的并非是最优解(贪心得到的解是 5 枚硬币)
 * <p>
 * - 假设 dp(n) 是凑到 n 分需要的最少硬币个数
 * 如果第 1 次选择了 25 分的硬币，那么 dp(n) = dp(n – 25) + 1
 * 如果第 1 次选择了 20 分的硬币，那么 dp(n) = dp(n – 20) + 1
 * 如果第 1 次选择了 5 分的硬币，那么 dp(n) = dp(n – 5) + 1
 * 如果第 1 次选择了 1 分的硬币，那么 dp(n) = dp(n – 1) + 1
 * 所以 dp(n) = min { dp(n – 25), dp(n – 20), dp(n – 5), dp(n – 1) } + 1
 */
public class 找零钱 {
    public static void main(String[] args) {
        int[] face = {5, 20, 25};
        System.out.println(coins4(41, face));
    }

    /**
     * 暴力递归, (自顶向下的调用，出现了重叠子问题)
     *
     * @param n
     * @return
     */
    static int coins1(int n) {
        if (n < 1) return Integer.MAX_VALUE;
        if (n == 25 || n == 20 || n == 5 || n == 1) return 1;

        int min1 = Math.min(coins1(n - 25), coins1(n - 20));
        int min2 = Math.min(coins1(n - 5), coins1(n - 1));
        return Math.min(min1, min2) + 1;
    }

    /**
     * 记忆化搜索, (自顶向下的调用)
     *
     * @param n
     * @return
     */
    static int coins2(int n) {
        if (n < 1) return -1;
        int[] dp = new int[n + 1];
        int[] faces = {1, 5, 20, 25};
        for (int face : faces) {
            if (n < face) break;
            dp[face] = 1;
        }

        return coins2(n, dp);
    }

    static int coins2(int n, int[] dp) {
        if (n < 1) return Integer.MAX_VALUE;
        if (dp[n] == 0) {
            int min1 = Math.min(coins2(n - 25, dp), coins2(n - 20, dp));
            int min2 = Math.min(coins2(n - 5, dp), coins2(n - 1, dp));
            dp[n] = Math.min(min1, min2) + 1;
        }
        return dp[n];
    }

    /**
     * 递推, (自底向上 迭代)
     *
     * @param n
     * @return
     */
    static int coins3(int n) {
        if (n < 1) return -1;
        int[] dp = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            int min = Integer.MAX_VALUE;
            if (i >= 1) min = Math.min(dp[i - 1], min);
            if (i >= 5) min = Math.min(dp[i - 5], min);
            if (i >= 20) min = Math.min(dp[i - 20], min);
            if (i >= 25) min = Math.min(dp[i - 25], min);
            dp[i] = min + 1;
        }
        return dp[n];
    }

    /**
     * 可以传入自己的零钱数组
     *
     * @param n
     * @param faces
     * @return
     */
    static int coins4(int n, int[] faces) {
        if (n < 1 || faces == null || faces.length == 0) return -1;
        int[] dp = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            int min = Integer.MAX_VALUE;
            for (int face : faces) {
                if (i < face || dp[i - face] < 0) continue;
                min = Math.min(dp[i - face], min);
            }
            if (min == Integer.MAX_VALUE){
                dp[i] = -1;
            }else {
                dp[i] = min + 1;
            }
        }
        return dp[n];
    }
}
